package com.example.demo.leetcode100题;

import com.example.demo.StopWatchTemplate;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author：zzc
 * @date: 2022/9/4
 */
public class 二叉树的中序遍历 {

    //给定一个二叉树的根节点 root ，返回它的 中序 遍历。
    //示例 1：
    //输入：root = [1,null,2,3]
    //输出：[1,3,2]
    //示例 2：
    //输入：root = []
    //输出：[]
    //示例 3：
    //输入：root = [1]
    //输出：[1]

    // 左 中 右
    public static void main(String[] args) {

        System.out.println(StopWatchTemplate.doSupplier(() -> binTreeInOrderTraversal2(new TreeNode())));
    }

    private static ArrayList<Integer>  binTreeInOrderTraversal2(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack  = new LinkedList<>();

        while (root != null ||!stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }

        return res;
    }

    private static LinkedList<Integer> binTreeInOrderTraversal(TreeNode treeNode) {
        if (treeNode == null) {
            return null;
        }

        LinkedList<Integer> list = new LinkedList<>();
        accessTree(treeNode, list);
        return list;


    }

    private static void accessTree(TreeNode treeNode, LinkedList<Integer> res) {
        if (treeNode == null) {
            return;
        }
        accessTree(treeNode.left, res);
        res.add(treeNode.val);
        accessTree(treeNode.right, res);

    }




}
